\section{\name Description}

%
\subsection{Model}
In addition to the two entities of the Mixcoin protocol, our protocol requires another entity, the public log. We summarize the entities present in the system below:

\subsubsection{Public Mix.} The public mix, \mix, is assumed to have a long standing public key \mixpubkey and associated private key \mixprivkey. The model assumes that there are many such mixes that will compete. Those mixes that have poor reputations will be less likely to be chosen by users, lest they get cheated. Thus, a mix is incentivized to participate in the protocol without allowing any proof of cheating to be made public.
\subsubsection{The User.} The user, \user, is a party that has an amount of Bitcoins in an address \inaddr (possibly linked to their true identity) and wishes to transfer the coins to a different address \outaddr, such that it is hard to link the addresses \inaddr and \outaddr. The user is also able to post anonymously to the public log with an alternate identity, \anonuser. This could be achieved through Tor, for example \cite{tor}. The user must be careful not to allow \user and \anonuser to be linked in any way.
\subsubsection{Public Log.} The public log, \publog, is a public, append-only log used for third party verification purposes. If a party breaches protocol, the public log will contain enough information to incriminate the misbehaving party. Anyone can post to the log, and messages can never be erased once they are posted. Each message is also associated with a timestamp. One possible way to implement this would be within the Bitcoin block chain. To send a message, the sender could just transfer a small about of BTC to one or more addresses corresponding to the message. Of course, if the user wishes to post to the log anonymously, the coins must be sent from an address that cannot be linked back to the user's identity. A (now dead and defunct) service that did just this is the Bitcoin Message Service \cite{messageservice}. 

\subsection{Assumptions}
In order for the system to achieve its goals, we make the following assumptions:
\begin{itemize}
\item Users connect anonymously when participating in the protocol.
\item All cryptographic operations are commutative, as described in \cite{chaum-blind}. 
\item All participants in the protocol run under a synchronized clock maintained by the public log.
\end{itemize}

\subsection{Protocol} \label{subsec:protocol}
In this section, we describe the core protocol for the mixing of a single "chunk" of \user's funds. At a high level, the protocol proceeds as follows: the mix announces mix data, the user opts in to the mix, the mix sends a partial warranty back to the user, the user transfers funds, the mix completes the warranty by posting to the public log, the user unblinds the output address, and finally the mix transfers funds to the output address. See Fig. \ref{fig:protocol} for an illustration of the protocol. 

\input{parameters}
%
\paragraph{Setup.} The mix \mix publishes a set of \emph{mix data}, \mixdata, to the public log. This data includes times (\userpaydeadline,~\warrantydeadline,~\unblinddeadline,~\mixpaydeadline) by which different steps of the protocol must be completed; the chunk size, \chunksize, which is the amount of BTC that each user inputs into the transaction; \feerate, the fraction of user inputs that will be kept as a mixing fee; \nonce, a nonce which serves as the redundancy checking predicate for commutative encryption as described in \cite{chaum-blind}; and \confirmationdelay, the number of blocks that the mix requires to verify the user’s payments. All of these parameters are part of the original Mixcoin protocol, except for two additional time deadlines, and the nonce \nonce.
%
\paragraph{User Sends Offer.} See step (1). The user \user opts in to the mix by sending its \emph{offer} to \mix. The offer includes the mix data followed by a blinded \emph{token} \token. The token consists of the output address, a private, randomly selected nonce \crsnonce which is used for fee collection, and the nonce \nonce. The token is encrypted using a commutative encryption function \commencfun known only to \user (who also knows the inverse \commdecfun), in order to keep these values hidden. The offer has the following form: $(mixdata, [\token]_{\commencfun})$, where $\token = (\outaddr, \crsnonce, \nonce)$.
%
\paragraph{Mix Sends Partial Warranty.} See step (2a). If \mix accepts the offer, it sends a \emph{partial warranty} back to the user. The partial warranty consists of the blinded token, an escrow address for the user to pay to, and the mix data. This is all signed with \mixprivkey. The partial warranty has the form $\{[\token]_{\commencfun}, \escaddr, \mixdata\}_{\mixprivkey}$. Note that given this partial warranty the user cannot recover the signed token directly, since other fields were included in the signed message. 
%
\paragraph{Mix Rejects Offer.} See step (2b). If the mix rejects the offer, the user destroys the output address.
%
\paragraph{User Pays.} See step (3a). The user \user applies \mixpubkey to recover \escaddr. \user then transfers \chunksize coins from any input address \inaddr to \escaddr by time \userpaydeadline.
%
\paragraph{User Fails to Pay.} See step (3b). If the user fails to transer the funds on time, then both parties abort the protocol.
%
\paragraph{Mix Completes Warranty.} See step (4a). Once the user has transferred the funds, \mix must \emph{complete the warranty} by signing the blinded token and publishing it to the public log by time \warrantydeadline (which should be long enough after \userpaydeadline to allow the transaction to be at least \confirmationdelay blocks deep into the chain). By publishes a user's token, the mix is publicly acknowledging that the user did indeed transfer their funds to the escrow address on time. The fact that this is public allows any third party verifier to check that the mix has completed the warranty by time \warrantydeadline. The signed blinded token has the form $\{[\token]_{\commencfun}\}_{\mixprivkey}$.
%
\paragraph{Mix Fails to Complete Warranty. User Publishes Incriminating Evidence.} See step (4b). If \mix fails to publish a user \user's token by \warrantydeadline, \user can publish information to incriminate \mix. \user can present the following evidence: the partial warranty $\{[\token]_{\commencfun}, \escaddr, \mixdata\}_{\mixprivkey}$, the transaction $Transfer(\chunksize,~\inaddr,~\escaddr)$ present in the block chain before time \userpaydeadline, and the fact that the signed token was not published to the public log before \warrantydeadline (this may require an enumeration of all messages in the blockchain between times \userpaydeadline and \warrantydeadline). Any third party verifier can see that \mix has signed the partial warranty, confirm that someone has transferred funds to \escaddr, and verify that indeed no token of the correct form was published to the public log before \warrantydeadline, proving that \mix deviated from the protocol.
%
\paragraph{User Anonymously Unblinds Output Address.} See step (5). Once their signed blinded token of the form $\{[\token]_{\commencfun}\}_{\mixprivkey}$ has been published to the public log, \user can apply \commdecfun to recover the signed unblinded token $\{\token\}_{\mixprivkey} = \{\outaddr, \crsnonce, \nonce\}_{\mixprivkey}$. The user connects anonymously as user \anonuser and unblinds \outaddr by posting the signed unblinded token to the public log. The mix \mix can verify that the output address is valid, since when it decryptes the token with \mixpubkey it finds the redundancy checking predicate \nonce within. If \anonuser fails to publish the unblinded token to the public log by time \unblinddeadline, \mix can choose to either refund the coins back to \user or retain them. Since \user breached the protocol, it cannot produce evidence to incriminate \mix, so \mix can do as it pleases with the funds.
%
\paragraph{Mix Computes Beacon Function.} At this point, \mix computes a beacon function $\crsrandfunc(\unblinddeadline, \confirmationdelay, \crsnonce)$ for each $[\outaddr, \crsnonce]$ pair to determine which output addresses to collect mixing fees from (by not sending any coins to them). The beacon function, as described in \cite{mixcoin}, is a publicly verifiable function that uses entropy collected from the block chain to produce a number uniformly in the range $[0, 1]$. Then, if the value for a particular input is less than or equal to the value $\feerate$ from the mix data, the chunk destined for that output address is kept by \mix as a mixing fee. Otherwise, the protocol proceeds to the next step.
%
\paragraph{Mix Pays to Output Address.} See step (6a). If \mix acts honestly, then before time \mixpaydeadline it will transfer \chunksize BTC to all unblinded output addresses that have passed the \crsrandfunc function. The mix does not know which input and output addresses are from the same user, so the mapping from input to output addresses does not matter.
%
\paragraph{Mix Steals Coins.} See step (6b). \mix steals the funds and fails to transfer a chunk to each of the output addresses by time \mixpaydeadline.
%
\paragraph{User Detects Theft and Publishes Incriminating Evidence.} See step (7). The user \user detects the theft at time \mixpaydeadline (since no funds were transferred to its output address), and can publish information to incriminate \mix. The user publishes the following: the commutative encryption function \commencfun and its inverse \commdecfun, the partial warranty $\{[\token]_{\commencfun}, \escaddr, \mixdata\}_{\mixprivkey}$ in the public log, the transaction $Transfer(\chunksize,~\inaddr,~\escaddr)$ present in the block chain before time \userpaydeadline, the signed token $\{\outaddr, \crsnonce, \nonce\}_{\mixprivkey}$, and the fact that no such transaction $Transfer(\chunksize,~\escaddr',~\outaddr)$ is present in the block chain before time \mixpaydeadline. Any third party verifier can decrypt the signed warranty with the \mixpubkey and remove the commutative encryption using \commdecfun. Then, the verifier can check the public log and the block chain to see if both parties followed the protocol.
%
\input{figure_protocol}
